package main;
import java.util.ArrayList;


public class SubsetGenerator {
	private int setSize = 0; // n po k
	private int subsetSize = 0;
	private int[] previous;
	private int p;
	private boolean first = true;
	 
	public SubsetGenerator(int sSize, int subSize){
		this.setSize = sSize;
		this.subsetSize = subSize;
		this.p = subSize-1;
		previous = new int[sSize];
	 }
	
	public boolean hasNext(){
		if(setSize < 1 || subsetSize < 1)
			return false;
		else if(setSize < subsetSize)
			return false;
		else if(setSize == subsetSize){
			return first;
		}
		if(updateP() >= 0)
			return true;
		return false;
	}
	 
	private void print(int[] tab) {
		String tmp = "";
		for (int i = 0; i <subsetSize; i++) {
			tmp += tab[i];
		}
		System.out.println(tmp);
	}
	
	private void addSubset(ArrayList<int[]> subsets, int[] tab){
		int subset[] = new int[subsetSize];
		for (int i = 0; i < subsetSize; i++) {
			subset[i] = tab[i];
		}
		subsets.add(subset);
	}
	
	private int[] getSubset(int[] tab){
		int subset[] = new int[subsetSize];
		for (int i = 0; i < subsetSize; i++) {
			subset[i] = tab[i];
		}
		return subset;
	}

	public ArrayList<int[]> generateAll() {
		
		int tab[] = new int[setSize];
		ArrayList<int[]> subsets = new ArrayList<int[]>();
		
		// verify parameters
		if(setSize < 1 || subsetSize < 1)
			return null;
		else if(setSize < subsetSize)
			return null;
		
		// init table
		for (int i = 0; i < setSize; i++) {
			tab[i] = i + 1;
		}
		
		// equal params
		if(setSize == subsetSize){
//			print(tab);
			addSubset(subsets, tab);
			return subsets;		
		}
		
		int p = subsetSize-1;
		while (p >= 0) {
//			print(tab);
			addSubset(subsets, tab);
			
			if (tab[subsetSize-1] == setSize){ // if tab[last] = setSize, move pointer 'p' left
				p = p - 1;									
			} else
				p = subsetSize-1;

			if (p >= 0){
				for (int i = subsetSize-1; i >= p; i--) {
					tab[i] = tab[p] + i - p + 1;
				}
			}
		}
		return subsets;
	}
	
	private int updateP(){
		if (previous[subsetSize-1] == setSize){ // if tab[last] = setSize, move pointer 'p' left
			p = p - 1;									
		} else
			p = subsetSize-1;
		return p;
	}
	
	public int[] getNext(){
		if(first){
			first = false;
			for (int i = 0; i < setSize; i++) {
				previous[i] = i + 1;
			}
//			print(previous);
			return getSubset(previous);
		}		

		for (int i = subsetSize-1; i >= p; i--) {
			previous[i] = previous[p] + i - p + 1;			
		}
		
//		print(previous);
		return getSubset(previous);
	}

}
